/*
 * @lc app=leetcode.cn id=380 lang=javascript
 *
 * [380] O(1) 时间插入、删除和获取随机元素
 */

// @lc code=start
// hashmap 记录元素和下标
// list 用于快速返回随机数
// 删除时,把最后一个元素和需要删除的元素位置对调,然后删除最后一个元素
var RandomizedSet = function() {
  this.map = new Map()
  this.list = []
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
  if (this.map.has(val)) return false
  this.list.push(val)
  this.map.set(val, this.list.length - 1)
  return true
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
  if (!this.map.has(val)) return false
  let m = this.map.get(val)
  let last = this.list[this.list.length - 1]
  this.list[m] = last
  this.map.set(last, m)
  this.map.delete(val)
  this.list.pop()
  return true
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
  return this.list[Math.floor(Math.random() * this.list.length)]
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
// @lc code=end

